﻿// 蒙图版钻石问题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <time.h>
using namespace std;

const int MAX_SIZE = 1000000;
const int MAX_VALUE = 100;

int init(int**& map, int**& answer_map, int& size);
int GA(int** map, int size);
int DP(int** map, int** answer_map, int size);
int GA_m(int** map, int** answer_map, int size, int m);
int DP_m(int** map, int** answer_map, int size, int i, int j);
int main()
{
	int size, m, ** map, ** answer_map;
	int res = init(map, answer_map, size);
	if (res == -2)
	{
		printf("input illeGA_ml!");
		exit(1);
	}
	else if (res == -1)
	{
		printf("init false!");
		exit(1);
	}

	clock_t start, finish;
	double totaltime;
	start = clock();
	int GA_answer = GA(map, size);
	finish = clock();
	totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
	cout << "GA answer:" << GA_answer << endl;
	cout << "run time:" << totaltime << endl;
	start = clock();
	int DP_answer = DP(map, answer_map, size);
	finish = clock();
	totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
	cout << "DP answer:" << DP_answer << endl;
	cout << "run time:" << totaltime << endl;
	cout << "please input size(less than size):";
	cin >> m;
	if (m >= size)
	{
		printf("input illeGA_ml!");
		exit(1);
	}
	start = clock();
	int GA_m_answer = GA_m(map, answer_map, size, m);
	finish = clock();
	totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
	cout << "GA_m answer:" << GA_m_answer << endl;
	cout << "run time:" << totaltime << endl;

	for (int i = 0; i < size; i++) {
		free(map[i]);
		free(answer_map[i]);
	}
	free(map);
	free(answer_map);
	return 0;
}

int GA_m(int** map, int** answer_map, int size, int m) {
	int answer = map[0][0], i = 0, j = 0;
	printf("[%d][%d]:%d ", i, j, map[i][j]);
	// 贪心算法选择这一步的走法，并根据新探测到的矿藏调整采矿预期结果
	for (int a = 1; a < size; a++) {
		if (i + j + m <= size - 1)
			DP_m(map, answer_map, m + 1, i, j);
		if (answer_map[i + 1][j] >= answer_map[i][j + 1]) {
			answer = answer + map[i + 1][j];
			i = i + 1;
		}
		else {
			answer = answer + map[i][j + 1];
			j = j + 1;
		}
		printf("-> [%d][%d]:%d ", i, j, map[i][j]);
	}
	printf("\n");
	return answer;
}

int GA(int** map,int size) {
	int answer = map[0][0], i = 0, j = 0;
	printf("[%d][%d]:%d ", i, j, map[i][j]);
	for (int a = 1; a < size; a++) {
		if (map[i + 1][j] >= map[i][j + 1]) {
			answer = answer + map[i + 1][j];
			i = i + 1;
		}
		else {
			answer = answer + map[i][j + 1];
			j = j + 1;
		}
		printf("-> [%d][%d]:%d ", i, j, map[i][j]);
	}
	printf("\n");
	return answer;
}

int DP(int** map, int** answer_map, int size) {
	for (int a = size - 1; a >= 0; a--)
		answer_map[a][size - 1 - a] = map[a][size - 1 - a];
	for (int a = size - 2; a >= 0; a--) {
		for (int b = 0; b <= a; b++) {
			if (answer_map[a - b + 1][b] >= answer_map[a - b][b + 1])
				answer_map[a- b][b] = map[a - b][b] + answer_map[a - b + 1][b];
			else
				answer_map[a - b][b] = map[a - b][b] + answer_map[a - b][b + 1];
		}
	}
	int i = 0, j = 0;
	printf("[%d][%d]:%d ", i, j, map[i][j]);
	for (int a = 1; a < size; a++) {
		if (answer_map[i + 1][j] >= answer_map[i][j + 1])
			i = i + 1;
		else 
			j = j + 1;
		printf("-> [%d][%d]:%d ", i, j, map[i][j]);
	}
	return answer_map[0][0];
}

int DP_m(int** map, int** answer_map, int size, int i, int j) {
	for (int a = size - 1; a >= 0; a--)
		answer_map[i + a][j + size - 1 - a] = map[i + a][j + size - 1 - a];
	for (int a = size - 2; a >= 0; a--) {
		for (int b = 0; b <= a; b++) {
			if (answer_map[i + a - b + 1][j + b] >= answer_map[i + a - b][j + b + 1])
				answer_map[i + a - b][j + b] = map[i + a - b][j + b] + answer_map[i + a - b + 1][j + b];
			else
				answer_map[i + a - b][j + b] = map[i + a - b][j + b] + answer_map[i + a - b][j + b + 1];
		}
	}
	return answer_map[i][j];
}

int init(int**& map, int**& answer_map, int& size) {
	ofstream outfile("test.txt");
	cout << "please input size(less than 1000,000):";
	cin >> size;
	if (size > MAX_SIZE)
		return -2;
	map = (int**)malloc(sizeof(int*) * size);
	answer_map = (int**)malloc(sizeof(int*) * size);
	if (map == NULL || answer_map == NULL)
		return -1;
	for (int i = 0; i < size; i++) {
		map[i] = (int*)malloc(sizeof(int) * (size - i));
		answer_map[i] = (int*)malloc(sizeof(int) * (size - i));
		if (map[i] == NULL || answer_map[i] == NULL)
			return -1;
		for (int j = 0; j < size - i; j++) {
			map[i][j] = rand() % MAX_VALUE;
			outfile << map[i][j] << "\t";
		}
		outfile << endl;
	}
	return 0;
}